package cn.zhl.algorithm._2_动态规划;

/**
 * @program: demos
 * @description: 走步数，只能右下，多少种走法
 * @author: 刘振华
 * @create: 2020-09-15 11:07
 **/
public class StepNums {
	public static void main(String[] args) {
//		System.out.println(steps(1,1));
		System.out.println(stepsFor(2,3));
	}

	static int stepsFor(int x,int y){
		if( x < 1 || y < 1 ){
			return -1;
		}
		int[][] grid = new int[x+1][y+1];
//		grid[0][0] = 1;
		int len = x>y?x:y;
		for(int i = 1; i <= len; i++){
			if(x>=i) {
				grid[i][0] = 1;
			}
			if(y>=i) {
				grid[0][i] = 1;
			}
		}
		for(int h = 1; h <= x; h++){
			for(int s = 1; s <= y; s++){
				grid[h][s] = grid[h-1][s]+grid[h][s-1];
			}
		}
		return grid[x][y];
	}

	static int steps(int x,int y){
		int[][] tables = new int[5][5];
//		tables[0][0] = 1;
		tables[0][1] = 1;
		tables[0][2] = 1;
		tables[0][3] = 1;
		tables[0][4] = 1;
		tables[1][0] = 1;
		tables[2][0] = 1;
		tables[3][0] = 1;
		tables[4][0] = 1;
		steps(tables,x,y);
		return tables[x][y];
	}
	static int steps(int[][] tables,int x,int y){
		if(x < 0 || y < 0) {
			return 0;
		}
		if(tables[x][y] == 0){
			tables[x][y] = steps(tables,x-1,y)+steps(tables, x, y-1);
		}
		return tables[x][y];
	}
}
